package com.example.leetcode.graph;

class UnionFind {

    int[] root;
    int[] rank;
    int count;

    public UnionFind(int size) {
        root = new int[size];
        rank = new int[size];
        count = size;
        for (int i = 0; i < size; i++) {
            root[i] = i;
            rank[i] = 1;
        }
    }

    public int find(int x) {
        if (root[x] == x) {
            return x;
        }
        int temp = find(root[x]);
        root[x] = temp;
        return temp;
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[x] > rank[y]) {
                root[rootY] = rootX;
            } else if (rank[x] < rank[y]) {
                root[rootX] = rootY;
            } else {
                root[rootX] = rootY;
                rank[rootY]++;
            }
            count--;
        }
    }

    public int getCount() {
        return count;
    }

    /**
     * 等价于方法 getCount()
     *
     * @return
     */
    public int rootCount() {
        int count = 0;
        for (int i = 0; i < root.length; i++) {
            if (root[i] == i) {
                count++;
            }
        }
        return count;
    }

}

class Solution547 {
    public int findCircleNum(int[][] isConnected) {
        // 深度优先遍历
//        return GraphUtils.findCircleNum(isConnected);
        // 广度优先遍历
//        return GraphUtils.findCircleNum2(isConnected);
        // 并查集
//        return GraphUtils.findCircleNum3(isConnected);
        return findCircleNumByUnionFind(isConnected);
    }

    private int findCircleNumByUnionFind(int[][] isConnected) {
        int n = isConnected.length;
        UnionFind unionFind = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (isConnected[i][j] == 1) {
                    unionFind.union(i, j);
                }
            }
        }
        return unionFind.rootCount();
    }
}

public class leetcode547 {
    public static void main(String[] args) {
        Solution547 solution547 = new Solution547();
        int[][] isConnected = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
        System.out.println(solution547.findCircleNum(isConnected));
    }
}
